/*
 * @lc app=leetcode.cn id=146 lang=cpp
 *
 * [146] LRU 缓存
 */
#include <unordered_map>

// @lc code=start
struct LinkNode {
    int key = 0;
    int value = 0;
    LinkNode *pre = nullptr;
    LinkNode *next = nullptr;
    LinkNode(int k, int v) : key(k), value(v) {};
    LinkNode() = default;
};

class double_list
{
  private:
    LinkNode *head = nullptr;
    LinkNode *tail = nullptr;

  public:
    double_list()
    {
        head = new LinkNode;
        tail = new LinkNode;
        head->next = tail;
        tail->pre = head;
    }

    LinkNode *push_front(LinkNode *node)
    {
        node->next = head->next;
        head->next->pre = node;
        node->pre = head;
        head->next = node;

        return node;
    }

    void move_to_head(LinkNode *node)
    {
        erase(node);
        push_front(node);
    }
    void erase(LinkNode *node)
    {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    LinkNode *pop_back()
    {
        LinkNode *tmp = tail->pre;
        erase(tmp);
        return tmp;
    }
};

class LRUCache
{
  private:
    int capacity = 0;
    int size = 0;
    double_list *my_list = nullptr;
    std::unordered_map<int, LinkNode *> my_map;

  public:
    LRUCache(int capacity)
    {
        this->capacity = capacity;
        my_list = new double_list;
    }

    int get(int key)
    {
        if (my_map.count(key)) {
            my_list->erase(my_map[key]);
            my_list->push_front(my_map[key]);
            return my_map[key]->value;
        }
        return -1;
    }

    void put(int key, int value)
    {
        if (my_map.count(key)) {
            my_map[key]->value = value;
            my_list->move_to_head(my_map[key]);
        } else {
            ++size;
            if (size > capacity) {
                LinkNode *node = my_list->pop_back();
                my_map.erase(node->key);
                delete node;
                --size;
            }
            my_map[key] = my_list->push_front(new LinkNode(key, value));
        }
    }
};
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// @lc code=end
